package leetcode.D100.T10;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-20 22:49:10 星期日
 */

class Solution {
    /**
     * 一刷
     * 思路：
     * 1. 先将p分割成一个个pattern：
     *      1. if 后面无*，则将这个字符直接作为一个pattern
     *      2. if 后面带*，则将该字符与*组成一个pattern
     *          2.1 ('a'-'z')* ---> 'A'-'Z'
     *          2.2 '.'*     ---> '-'
     * 2. 动态规划，创建一个dp[patterns.length][s.size()]dp[i][j-1]、dp[i-1][j]计算，只要某一个为true，且经过judge判断为true，则dp[i][j]为true，否则为false
     *     2.0 dp[i][j]的含义：patterns[0~i]与s[0~j]是否匹配（a[i~j]表示a[i]~a[j-1]）
     *     2.1 状态转移方程：根据dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]，以及judge的结果来求出dp[i][j]
     *          - if dp[i-1][j-1]==true，则判断patterns[i-1]是否能匹配s[j-1]，如果能则dp[i][j]为true
     *          - if 上一步不成立，且dp[i][j-1]==true，则判断patterns[i-1]是否能“继续”匹配s[j-1]，这要求patterns[i-1]必须带*，否则不行。如果可以，则dp[i][j]为true
     *          - if 上一步不成立，且dp[i-1][j]==true，则判断patterns[i-1]是否能匹配“空字符串”（表示为0），如果能则dp[i][j]为true
     *     2.2 最终结果：dp[patterns.length-1][s.size()-1]
     *     2.3 2.1中的判断方法（judge），给定一个target字符和pattern，判断是否能够匹配。注意第二个判断中需要判断是否能“继续”匹配，需要特殊处理
     *          2.3.1 如果是判断能否“继续”匹配，则判断pattern是否带*，如果不带*，说明pattern无法在已经匹配别的字符下，再匹配target了
     *          2.3.2 如果不是“继续”匹配，进行普通处理即可，需要注意target为空字符（0）的情况
*          2.3 上面的算法空间复杂度为O(m*n)，可以进一步优化为O(n)
     */
    /*public boolean isMatch(String s, String p) {
        char[] patterns = getPatterns(p);       // 分割p，得到pattern数组
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 0; i<patterns.length; ++i) {
            boolean last = dp[0];
            if (dp[0])
                dp[0] = judge((char)0, patterns[i], false);
            for(int j = 1; j<dp.length; ++j) {
                boolean flag = false;
                if (last && judge(s.charAt(j-1), patterns[i], false))
                    flag = true;
                if (!flag && dp[j-1] && judge(s.charAt(j-1), patterns[i], true))
                    flag = true;
                if (!flag && dp[j] && judge((char)0, patterns[i], false))
                    flag = true;
                last = dp[j];
                dp[j] = flag;
            }
        }
        return dp[dp.length-1];
    }

    private char[] getPatterns(String p) {
        int n = 0;
        for(int i=0; i<p.length(); ++i) {
            if (p.charAt(i) == '*')
                n++;
        }
        char[] patterns = new char[p.length()-n];
        int i = p.length()-1, j = p.length()-n-1;
        while (i >= 0) {
            if (p.charAt(i) == '*') {
                if (p.charAt(i-1) == '.')
                    patterns[j--] = '-';
                else
                    patterns[j--] = (char) (p.charAt(i-1) - 'a' + 'A');
                i -= 2;
            } else {
                patterns[j--] = p.charAt(i);
                i--;
            }
        }
        return patterns;
    }

    private boolean judge(char target, char pattern, boolean more) {
        if (more) {     // “继续”匹配模式
            if (pattern >= 'A' && pattern <= 'Z')
                return target == ((char) pattern-'A'+'a');
            if (pattern == '-')
                return true;
            return false;
        }
        if (pattern == '-')
            return true;
        else if (pattern == '.')
            return target != ((char) 0);
        else if (pattern >= 'A' && pattern <= 'Z') {
            if(target == (char) 0)
                return true;
            else
                return target == ((char) pattern-'A'+'a');
        }
        else
            return target == pattern;
    }*/

    // 二刷
    public boolean isMatch(String s, String p) {
        char[] pattern = getPattern(p);
        boolean[] dp = new boolean[pattern.length+1];
        dp[0] = true;
        for (int i=1; i<=pattern.length; ++i) {
            if (dp[i-1] && judge('-', pattern[i-1], false))
                dp[i] = true;
        }
        for (int i=0; i<s.length(); ++i) {
            boolean last = dp[0];
            dp[0] = false;
            for (int j=1; j<=pattern.length; ++j) {
                boolean temp = dp[j];
                if (last && judge(s.charAt(i), pattern[j-1], false)) {
                    dp[j] = true;
                } else if (dp[j-1] && judge('-', pattern[j-1], false)) {
                    dp[j] = true;
                } else if (dp[j] && judge(s.charAt(i), pattern[j-1], true)) {
                    dp[j] = true;
                } else {
                    dp[j] = false;
                }
                last = temp;
            }
        }
        return dp[dp.length-1];
    }

    private char[] getPattern(String p) {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<p.length(); ++i) {
            if (p.charAt(i) == '.') {
                if (i + 1 < p.length() && p.charAt(i+1) == '*')
                    sb.append('+');
                else
                    sb.append('.');
            } else if (p.charAt(i) != '*') {
                if (i + 1 < p.length() && p.charAt(i+1) == '*')
                    sb.append((char) (p.charAt(i) + 'A' -'a'));
                else
                    sb.append(p.charAt(i));
            }
        }
        return sb.toString().toCharArray();
    }

    private boolean judge(char target, char pattern, boolean isMore) {
        if (pattern == '+')
            return true;
        if (target == '-') {
            if (pattern >= 'A' && pattern <= 'Z')
                return true;
            return false;
        }
        if (isMore) {
            if (pattern >= 'A' && pattern <= 'Z') {
                char p = (char) (pattern - 'A' + 'a');
                return p == target;
            }
            return false;
        }
        if (pattern == '.')
            return true;
        char p = (pattern >= 'A' && pattern <= 'Z') ? (char) (pattern - 'A' + 'a') : pattern;
        return target == p;
    }
}
